//
// Created by 麻再挺 on 2021/12/20.
//

#include "hash_search.h"

/**
 * 哈希表默认的哈希函数
 * @param key 键
 * @return
 */
size_t Hash_Table_Default(HashKeyType key) {
    return key % HASH_MAX_SIZE;
}

/**
 * 哈希表初始化
 * @param ht 哈希表
 */
void Hash_Table_Init(HashTable *ht) {
    if (ht == NULL)return;
    ht->size = 0;
    ht->hashFunc = Hash_Table_Default;
    for (int i = 0; i < HASH_MAX_SIZE; ++i) {
        ht->data[i].key = 0;
        ht->data[i].stat = Empty;
        ht->data[i].value = 0;
    }
}

/**
 * 哈希表插入元素
 * @param ht 哈希表
 * @param key 键
 * @param value 值
 * @return
 */
int Hash_Table_Insert(HashTable *ht, HashKeyType key, HashValueType value) {
    if (ht == NULL) return 0;
    // 判断哈希表内容是否超出了负载
    if (ht->size >= HASH_MAX_SIZE * LOAD_FACTOR) return 0;
    // 先将哈希函数将 key 转换, 求得 key 在哈希表中的下标
    int cur = ht->hashFunc(key);
    // 判断下标是否被占用
    while (1) {
        // 保证不会用重复的数字存入哈希表
        if (ht->data[cur].key == key) return 0;
        if (ht->data[cur].stat != Valid) {
            ht->data[cur].key = key;
            ht->data[cur].value = value;
            ht->data[cur].stat = Valid;
            ht->size++;
            return 1;
        }
        cur++;
    }
}

/**
 * 哈希表查找, 找到返回 1，并返回结点的值；未找到返回 0
 * @param ht 哈希表
 * @param key 键
 * @param value 值
 * @param cur 位置
 * @return
 */
int Hash_Table_Find(HashTable *ht, HashKeyType key, HashValueType *value) {
    if (ht == NULL) return 0;
    // 通过哈希函数找到 key 的下标
    int offset = ht->hashFunc(key);
    // 若当前下标对应的值正好是 key 的值, 并且当前的状态必须是valid才返回
    if (ht->data[offset].key == key && ht->data[offset].stat == Valid) {
        *value = ht->data[offset].value;
        return offset;
    } else {
        // 若当前下标所对应的值不是 key, 则继续向后进行查找, 直到找到 stat == empty
        while (ht->data[offset].stat != Empty) {
            // 如果 key 不等,则索引向右偏移
            if (ht->data[offset].key != key) {
                // 向右查找
                offset++;
                // 判断下标是否已超出最大值
                if (offset >= HASH_MAX_SIZE) offset = 0;
            } else {
                // 如果有效, 则赋值
                if (ht->data[offset].stat == Valid) {
                    *value = ht->data[offset].value;
                    return offset;
                } else {
                    offset++;
                }
            }
        }
    }
    return 0;
}

/**
 * 查询 key 所在的位置
 * @param ht 哈希表
 * @param key 键
 * @param cur 位置
 * @return
 */
int Hash_Table_Find_Cur(HashTable *ht, HashKeyType key, int *cur) {
    if (ht == NULL) return 0;
    for (int i = 0; i < HASH_MAX_SIZE; ++i) {
        if (ht->data[i].key == key && ht->data[i].stat == Valid) {
            *cur = i;
            return i;
        }
    }
    return 0;
}

/**
 * 哈希表删除数据
 * @param ht 哈希表
 * @param key 键
 */
void Hash_Table_Remove(HashTable *ht, HashKeyType key) {
    if (ht == NULL) return;
    // 先查找 key 是否存在
    int cur = 0;
    int ret = Hash_Table_Find_Cur(ht, key, &cur);
    if (ret == 0) return;
    else {
        ht->data[cur].stat = InValid;
        ht->size--;
    }
}

/**
 * 判断哈希表是否为空
 * @param ht 哈希表
 */
Status Hash_Table_Empty(HashTable *ht) {
    if (ht == NULL) {
        return 0;
    } else {
        return ht->size > 0 ? OK : ERROR;
    }
}

/**
 * 计算哈希表大小
 * @param ht 哈希表
 * @return
 */
size_t Hash_Table_Size(HashTable *ht) {
    if (ht == NULL) return 0;
    return ht->size;
}

/**
 * 打印哈希表内容
 * @param ht 哈希表
 */
void Hash_Table_Print(HashTable *ht) {
    if (ht == NULL || ht->size == 0) return;
    for (int i = 0; i < HASH_MAX_SIZE; ++i) {
        if (ht->data[i].stat != Empty) {
            printf("[%d]  key=%d  value=%d  stat=%d\n", i, ht->data[i].key,
                   ht->data[i].value, ht->data[i].stat);
        }
    }
}